package com.zdb.datastructures.sort;

import com.zdb.datastructures.utils.MockDataUtils;
import com.zdb.datastructures.utils.TimeUtils;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
//        int[] arr = {-9,-567,70,-20,-22,-25};
//        int[] arr = {-9,20,30,40};
//        int[] arr = {-9,-20,-30,-40};
//        int[] arr = {-9,-20,-30,-40, -9};
        int[] arr = {-9,20,30,40, -9};
//        int[] arr = MockDataUtils.mock80000IntArr();
        TimeUtils.printNowStr();

        quickSort(arr, 0, arr.length -1);

        // 验证结果
        for (int i = 0; i < arr.length -1; i++) {
            if(arr[i] > arr[i+1]) {
                System.out.println("error:" + arr[i] + "," + arr[i+1]);
                return;
            }
        }

        System.out.println(Arrays.toString(arr));
        TimeUtils.printNowStr();

    }

    public static void quickSort(int[] arr,int low,int high){
        int l,r,temp,t;
        if(low>high){
            return;
        }
        // 左边指针
        l=low;
        // 右边指针
        r=high;
        //temp就是基准位
        temp = arr[low];

        while (l<r) {

            /** 很重要哦
            // 一定要先找右边，因为基准位为第一个，右边先找，
            // 会把r+1-> high的数据都符合(大于或者等于temp)，
            // 此时r指定位置的数据一定比temp小或者等于temp(因为temp放在了第一个),
            // 后续对r位置的处理有两种情况：
            // 1. l找到比temp大的数据，进行交换
            // 2. l找不到比temp大的数据，l=r,将l和r共同指向的数据和基准位的交换
            // 因此一定要先找右边，如果要想先找左边，那么基准位取数组的high
             */

            //先看右边，依次往左递减,直到找到比temp小的值
            while (temp<=arr[r]&&l<r) {
                r--;
            }
            //再看左边，依次往右递增，直到找到比temp大的值
            while (temp>=arr[l]&&l<r) {
                l++;
            }
            //如果满足条件则交换，说明各自找到了一个，进行交换
            if (l<r) {
                t = arr[r];
                arr[r] = arr[l];
                arr[l] = t;
            }

        }
        // 循环退出时，l = r;各自都指向了temp放的位置

        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[l];
        arr[l] = temp;
        //递归调用左半数组
        quickSort(arr, low, r-1);
        //递归调用右半数组
        quickSort(arr, r+1, high);
    }

}
